import java.util.Arrays;
// dijkstra算法

public class networkDelayTime {
    public int networkDelayTime(int[][] times, int n, int k) {
        final int INF = 1000000000;
        //创建一个图来记录边的关系
        int[][] g = new int[n][n];
        for (int i = 0; i < n; i++) {
            g[i] = new int[n];
            Arrays.fill(g[i], INF);
        }
        for (int i = 0; i < times.length; i++) {
            g[times[i][0] - 1][times[i][1] - 1] = times[i][2];
        }
        int maxDis = 0;
        int[] dis =  new int[n];
        Arrays.fill(dis, INF);
        boolean[] vis = new boolean[n];
        dis[k - 1] = 0;
        while(true){
            int u = -1;
            //找出最小的
            for (int i = 0; i < n; i++) {
                if (!vis[i] && (u == -1 || dis[i] < dis[u])) {
                    u = i;
                }
            }
            if(u == -1) return maxDis;
            if(dis[u] == INF) return -1;
            vis[u] = true;
            for (int v = 0; v < n; v++) {
                if(!vis[v] && dis[v] > dis[u] + g[u][v]){
                    dis[v] = dis[u] + g[u][v];
                }
            }
        }
    }
}
